<?php
/*
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。


提示：

0 <= nums.length <= 50000
0 <= nums[i] <= 10000

难度：简单

https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/


*/

$arr = [1,2,3,4,5,6,7,8];
$arr = [1,2,3,4,5,6,7];
$obj = new Code_Offer21();
$res = $obj->main($arr);
var_dump($res);

class Code_Offer21
{
    public function main($arr)
    {
        $len = count($arr);
        $left = 0;
        $right = $len - 1;
        while ($left < $right) {
            // left从左到右搜索偶数
            while ($left < $right && ($arr[$left] & 1) == 1) {
                $left++;
            }
            // right从右到左搜索奇数
            while ($left < $right && ($arr[$right] & 1) == 0) {
                $right--;
            }
            $tmp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $tmp;
        }
        return $arr;
    }
}